home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / plan_test.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  3KB  |  136 lines
  1. #include <LEDA/window.h>
  2. #include <LEDA/graph_alg.h>
  3. #include <LEDA/graph_edit.h>
  4.  
  5.  
  6. main()
  7. {
  8.   window W;
  9.   panel P;
  10.   
  11.   GRAPH<point,int>G;
  12.   node v,w;
  13.   edge e;
  14.   
  15.   int N = 1000;
  16.   int input= 0;
  17.   
  18.   P.choice_item("input",input,"edit","random");
  19.   P.int_item("|V| = ",N,0,2000);
  20.   
  21.   for(;;)
  22.   {
  23.     G.clear();
  24.  
  25.     P.open(5,5);
  26.     W.init(0,100,0);
  27.     
  28.     if(input == 1)
  29.       { W.set_node_width(3);
  30.         node_array<double> xcoord;
  31.         node_array<double> ycoord;
  32.         random_planar_graph(G,xcoord,ycoord,N);
  33.         node v;
  34.         forall_nodes(v,G) 
  35.            { xcoord[v] *= 100;
  36.              ycoord[v] *= 100;
  37.              W.draw_node(xcoord[v],ycoord[v]);
  38.             }
  39.     
  40.         edge e;
  41.         forall_edges(e,G)
  42.            W.draw_edge(xcoord[source(e)],ycoord[source(e)],
  43.                        xcoord[target(e)],ycoord[target(e)]);
  44.        }
  45.     else
  46.       { W.set_node_width(12);
  47.         graph_edit(W,G,false);
  48.        }
  49.     
  50.     
  51.     
  52.     W.del_message();
  53.     W.message(string("PLANARITY TEST  |V| = %d",G.number_of_nodes()));
  54.     
  55.     list<edge>L;
  56.     
  57.     if(Eplanar(G,L))
  58.     { 
  59.       if(G.number_of_nodes() < 4)
  60.         { W.clear();
  61.           W.message("That's an insult: Every graph with less than 4 nodes is planar");
  62.          }
  63.       else 
  64.         {
  65.           W.message("Graph is planar. I compute an embedding for you ... ");
  66.  
  67.     
  68.           node_array<int>nr(G);
  69.           edge_array<int>cost(G);
  70.           int cur_nr= 0;
  71.           int n= G.number_of_nodes();
  72.           node v;
  73.           edge e;
  74.           
  75.           forall_nodes(v,G)nr[v]= cur_nr++;
  76.           
  77.           forall_edges(e,G)cost[e]= ((nr[source(e)]<nr[target(e)])?
  78.           n*nr[source(e)]+nr[target(e)]:
  79.           n*nr[target(e)]+nr[source(e)]);
  80.           
  81.           G.sort_edges(cost);
  82.           
  83.           list<edge>L= G.all_edges();
  84.           
  85.           while(!L.empty())
  86.           { e= L.pop();
  87.     
  88.            if(!L.empty()&&(source(e)==target(L.head()))&&(source(L.head())==target(e)))
  89.                L.pop();
  90.            else 
  91.                G.new_edge(target(e),source(e));
  92.            }
  93.     
  94.      
  95.           make_biconnected(G);
  96.     
  97.           Planar(G);
  98.     
  99.           node_array<int> xcoord(G);
  100.           node_array<int> ycoord(G);
  101.  
  102.           STRAIGHT_LINE_EMBEDDING(G,xcoord,ycoord);
  103.     
  104.           forall_nodes(v,G) ycoord[v] *= 2;
  105.  
  106.           W.init(-1,2*G.number_of_nodes()+1,-1);
  107.     
  108.           if (input == 1)
  109.              forall_nodes(v,G) W.draw_node(xcoord[v],ycoord[v]);
  110.           else
  111.              { int i = 0;
  112.                forall_nodes(v,G) W.draw_int_node(xcoord[v],ycoord[v],i++);
  113.               }
  114.     
  115.           forall_edges(e,G)
  116.           W.draw_edge(xcoord[source(e)],ycoord[source(e)],
  117.                       xcoord[target(e)],ycoord[target(e)]);
  118.          }
  119.        }
  120.     else
  121.       {
  122.         W.message("Graph is not planar. I show you the Kuratowski subgraph");
  123.         W.set_line_width(5);
  124.         edge e;
  125.         forall(e,L)W.draw_edge(G[source(e)],G[target(e)]);
  126.         W.set_line_width(1);
  127.        }
  128.     
  129.    } //for(;;)
  130.   
  131.   
  132.   return 0;
  133.   
  134. }
  135.         
  136.